This invention relates to wireless networks, and more particularly to a routing method and apparatus for avoiding unnecessary retransmissions, such as those caused by loops, in a link-determined topology.
Wireless networks include a vast variety of network configurations, all characterized by the transmission of data through the air rather than through a cable. Wireless networks may include LANs (local area networks) as well as WANs (wide area networks) or the upcoming versions of LANs known as PANs (personal area networks).
Much of today""s wireless networking technology is directed to radio frequency (RF) signals, but microwave and infrared signals may also be used. Wireless communications can be passed with either analog or digital signaling.
xe2x80x9cPacket radioxe2x80x9d has been in use for many years, with packet radio networks comprised of conventional radios, each in communication with a computer and a modem. Messages are carried in packets and the radios forward each packet separately.
More recently, the transmission of packet data by radio has been accomplished with all kinds of radio-equipped computing equipment. Wireless network access is used by equipment such as 2-way data devices (messaging devices and personal digital assistants), data capable phones, and laptops and palmtops. Although each device may be mobile or stationary, by convention, they are often referred to as xe2x80x9cstationsxe2x80x9d.
In a multi-hop network, each station participates in forwarding messages to other stations, thereby extending the communication range of each station.
For wireless packet networks, routing protocols designed for wired networks are not generally satisfactory. Various methods may be used to determine the best path between two wireless devices. One approach to routing is source routing, where the sender of a message includes the routing with the message. Another approach is referred to as link-state or link-determined routing, in which the best path is determined by a router that executes some sort of routing algorithm.
An example of a link-determined routing method, first applied for packet radio networks, is known as Radio Shortest Path First (RSPF) routing. Roughly described, the RSPF protocol is designed for use by Internet layer routing nodes in a packet radio network using the Internet Protocol (IP). It is a way to make IP work with packet radio.
The result of link-determined routing is a link topology, which may have loops and other problematic structures. The problems associated with such structures are manifested in situations such as contention control, when messages are to be retransmitted. If messages are simply retransmitted from device to device, loops can cause messages to be cycled endlessly through the network, causing problems. This is especially true when the communication range of the communicating devices is short relative to the maximum pairwise distance between devices.
One aspect of the invention is a method of routing messages in a wireless communications network having a number of wireless communications devices. At least some of the devices having computation resources, which permit the device to interpret and respond to messages. Transmissions from each device are synchronized, such that all transmissions occur simultaneously. At each receiving device, a routing unit performs the following operations: storing each last transmitted message; checking incoming messages for integrity, such that any message comprised of different transmissions is designated as a corrupt message; discarding any corrupt messages; delivering each non-corrupt incoming message to the computation resources; receiving a potential outgoing message from the computation resources, comparing each potential outgoing message with the last transmitted message; using a rules engine to determine whether the potential outgoing message should be transmitted.
It may be that the computation resources do not modify the message, such that the potential outgoing message is the same as the incoming message. The rules engine is programmed to apply the following rules: the device may transmit only in response to receiving a transmission; the device may only receive after transmitting; the device repeats a received transmission unless it is configured to respond to the transmission; and the results of the comparing step are used to prevent the device from repeating a transmission.
In accordance with the invention, each device in the network performs routing tasks at the link level. A designated root device performs additional routing tasks. Specifically, transmissions are synchronized among all devices. Each device follows a set of rules that result in alternating send-listen cycles, permit collisions to be detected, and avoid unnecessary retransmissions.
As a result of the synchronized device-based routing control, collisions are allowed to occur. This is in contrast to other xe2x80x9ccollision avoidingxe2x80x9d routing methods. Unacceptable (corrupt) collisions (receiving different messages from multiple transmitters) are distinguished from acceptable collisions (receiving the same message from multiple transmitters). Unacceptable collisions may then be discarded, and acceptable collisions handled in a manner that avoids repeat transmissions.
An advantage of the invention is that it creates a tree-like topology and avoids loops associated with link-determined topologies. Routing is automatic; there is no need for routing tables. The computational cost at each device is low, and thus the invention may be inexpensively implemented.